/*************************************************************************
 * Header:
 *    Set Class : Lesson01
 * Summary:
 *    This class contains basic tools for a Set, a data structure that
 *    can hold different kinds of data.
 *
 *    This will contain the class definition(s) of:
 *        Set              : A class that holds stuff
 *        SetIterator      : Iterator through the Set
 * Author
 *    Spencer Memmott
 **************************************************************************/

#ifndef SET_H
#define SET_H

#include <cassert>

// Forward declaration for SetIterator
template <class T>
class SetIterator;

/************************************************
 * SET CLASS
 * A Set class that has the necessary
 * functions to allow the user to create and
 * manipulate a vector of data
 ************************************************/
template <class T>
class Set
{
private:
   T * data;        // Dynamically allocated array of T
   int numItems;    // How many items are currently in the Set?
   int maxCapacity; // How many items can I put on the Set before it's full?

public:
   // Default Constructor : Full of Empty data :)
   Set() : numItems(0), maxCapacity(0), data(0x00000000) {}
   // Non-default Constructor : Pre-allocate the Set
   Set(int maxCapacity) throw (const char *);
   // Destructor : Clean up the mess made
   ~Set()   { if (maxCapacity) delete [] data; }
   // Copy Constructor : Copy the Set
   Set(const Set & rhs)  throw (const char *);
   // Insert an item at the end of the Set
   void insert(const T & t) throw (const char *);
   // Is the Set empty?
   bool empty()    const { return numItems == 0; }
   // How many items are currently in the Set?
   int  size()     const { return numItems;      }
   // How many items can the Set currently hold?
   int  capacity() const { return maxCapacity;   }
   // Remove all the items in the Set
   void clear()          { numItems = 0;         }
   //
   void erase();
   // Assignment Operator
   Set & operator =  (const Set & rhs);
   // Set Intersection
   Set   operator && (const Set & rhs) const;
   // Set Union
   Set   operator || (const Set & rhs) const;
   // Return the iterator to the beginning of the list
   SetIterator <T> begin()  { return SetIterator<T>(data);                }
   // Return the iterator to the end of the list
   SetIterator <T> end()    { return SetIterator<T>(data + numItems);     }
   // Return the iterator to the reverse beginning of the list
   SetIterator <T> rbegin() { return SetIterator<T>(data + numItems - 1); }
   // Return the iterator to the reverse end of the list
   SetIterator <T> rend()   { return SetIterator<T>(data - 1);            }
   // Finds the given data and returns the iterator pointing to it
   SetIterator <T> find(const T & t);
};

/************************************************
 * SET ITERATOR CLASS
 * A Set Iterator class
 ************************************************/
template <class T>
class SetIterator
{
private:
   T * p; // Pointer for the Iterator

public:
   // Default Constructor
   SetIterator() : p(0x00000000) {}
   // Non-default Constructor
   SetIterator(T * p) : p(p) {}
   // Copy Constructor
   SetIterator(const SetIterator & rhs) { *this = rhs; }
   // Get the Pointer for the Iterator
   T * getP() { return p; }
   // Assignment Operator
   SetIterator & operator = (const SetIterator & rhs)
   {
      this->p = rhs.p;
      return *this;
   }
   // Prefix Increment
   SetIterator <T> & operator ++ ()
   {
      p++;
      return *this;
   }
   // Postfix Increment
   SetIterator <T> operator ++ (int postfix)
   {
      SetIterator tmp(*this);
      p++;
      return tmp;
   }
   // Prefix Decrement
   SetIterator <T> & operator -- ()
   {
      p--;
      return *this;
   }
   // Postfix Decrement
   SetIterator <T> operator -- (int postfix)
   {
      SetIterator tmp(*this);
      p--;
      return tmp;
   }
   // Not Equals Operator
   bool operator != (const SetIterator & rhs) const
   {
      return rhs.p != this->p;
   }
   // Is Equal Operator
   bool operator == (const SetIterator & rhs) const
   {
      return rhs.p == this->p;
   }
   // Dereference Operator
   T & operator * () { return *p; }
};

/************************************************
 * SET :: FIND
 ************************************************/
template <class T>
SetIterator <T> Set <T> :: find(const T & t)
{
   SetIterator <T> tmp = data + numItems;
   for (int i = 0; i < numItems; i++)
   {
      if (data[i] == t)
      {
         tmp = data + i;
      }
   }
   return tmp;
}


/*******************************************
 * SET :: COPY CONSTRUCTOR
 *******************************************/
template <class T>
Set <T> :: Set(const Set <T> & rhs) throw (const char *)
{
   assert(rhs.maxCapacity >= 0);
   // Do nothing if there is nothing to do
   if (rhs.maxCapacity == 0)
   {
      maxCapacity = numItems = 0;
      data = 0x00000000;
      return;
   }
   // Try to allocate space for Set
   try
   {
      data = new T[rhs.maxCapacity];
   }
   catch (std::bad_alloc)
   {
      throw "ERROR: Unable to allocate a new buffer for Set";
   }
   // Copy over the data
   assert(rhs.numItems >= 0 && rhs.numItems <= rhs.maxCapacity);
   maxCapacity = rhs.maxCapacity;
   numItems = rhs.numItems;
   for (int i = 0; i < numItems; i++)
      data[i] = rhs.data[i];
}

/**********************************************
 * SET : NON-DEFAULT CONSTRUCTOR
 * Preallocate the vector to "maxCapacity"
 **********************************************/
template <class T>
Set <T> :: Set(int maxCapacity) throw (const char *)
{
   assert(maxCapacity >= 0);
   // Do nothing if there is nothing to do
   if (maxCapacity == 0)
   {
      this->maxCapacity = this->numItems = 0;
      this->data = 0x00000000;
      return;
   }
   // Try to allocate space for Set
   try
   {
      data = new T[maxCapacity];
   }
   catch (std::bad_alloc)
   {
      throw "ERROR: Unable to allocate a new buffer for Set";
   }
   // Copy over the data
   this->maxCapacity = maxCapacity;
   this->numItems = 0;
}

/***************************************************
 * SET :: INSERT
 * Push back an item on the end of the container
 **************************************************/
template <class T>
void Set <T> :: insert(const T & t) throw (const char *)
{
   // Let's see if we can do this..
   try
   {
      // If the max capacity is zero..
      if (maxCapacity == 0)
      {
         // Set data to the new capacity
         data = new T[++maxCapacity];
      }
      // If the max capacity is less than or equal to
      // the number of items in the vector..
      else if (maxCapacity <= numItems)
      {
         // Create a new data array double the previous
         // capacity
         T * newData = new T[maxCapacity *= 2];
         // Copy the old data to the new data
         for (int i = 0; i < numItems; i++)
            newData[i] = data[i];
         // Delete the old data
         delete [] data;
         // Point the data array to the new data
         data = newData;
      }
      if (find(t) == end())
      {

      }
      /*
      if (find(t) == end())
      {
         int i, j;
         T * tmp;
         for (i = 1; i < numItems; i++)
         {
            j = i;
            while (j > 0 && data[j - 1] > data[j])
            {
               *tmp        = data[j];
               data[j]     = data[j - 1];
               data[j - 1] = *tmp;
               j--;
            }
         }
      }
      */
   }
   // If there was a problem allocating memory..
   catch (std::bad_alloc)
   {
      // Throw an error message
      throw "ERROR: Unable to allocate a new buffer for Set";
   }
   // Finally, if everything has worked so far, insert the given
   // data into the data array
   //data[numItems++] = t;

   return;
}

/***************************************************
 * SET :: ASSIGNMENT OPERATOR
 * Copy the data in one Set to another
 **************************************************/
template <class T>
Set <T> & Set <T> :: operator = (const Set & rhs)
{
   assert(rhs.maxCapacity >= 0);
   // Do nothing if there is nothing to do
   if (rhs.maxCapacity == 0)
   {
      maxCapacity = numItems = 0;
      data = 0x00000000;
      return;
   }
   // Try to allocate space for Set
   try
   {
      data = new T[rhs.maxCapacity];
   }
   catch (std::bad_alloc)
   {
      throw "ERROR: Unable to allocate a new buffer for Set";
   }
   // Copy over the data
   assert(rhs.numItems >= 0 && rhs.numItems <= rhs.maxCapacity);
   maxCapacity = rhs.maxCapacity;
   numItems = rhs.numItems;
   for (int i = 0; i < numItems; i++)
      data[i] = rhs.data[i];

   return *this;
}

/********************************************
 * SET && (INTERSECTION)
 * Return a new set representing the intersection
 * between this and rhs
 ********************************************/
template <class T>
Set <T> Set <T> :: operator && (const Set <T> & rhs) const
{
   Set s;                           // the new Array to be returned

   for (int i = 0; i < size(); i++) // go though all the items
      if (rhs.isMember(data[i]))    // if it is not present
         s += data[i];              // add it.

   return s;                        // return the new array by value
}

/********************************************
 * SET || (UNION)
 * Return a new set representing the union
 * between this and rhs
 ********************************************/
template <class T>
Set <T> Set <T> :: operator || (const Set <T> & rhs) const
{
   Set a(rhs);

   for (int i = 0; i < size(); i++)
      if (!a.isMember(data[i]))
         a += data[i];
   for (int i = 0; i < rhs.size(); i++)
      if (!a.isMember(rhs.get(i)))
         a += rhs.get(i);

   return a;
}

#endif // SET_H
